package com.major.huffman.huffmantree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class HuffmanTreeMain {
    public static void main(String[] args) {
        int[] arr = {3, 7, 8, 29, 5, 11, 23, 14};
        Node node = createHuffmanTree(arr);
        System.out.println(node);
    }

    public static Node createHuffmanTree(int[] arr) {
        // 将数组里的元素转换为若干个二叉树
        List<Node> nodes = new ArrayList<>();
        for (int val : arr) {
            nodes.add(new Node(val));
        }
        // 循环处理
        while (nodes.size() > 1) {
            // 排序
            Collections.sort(nodes);
            System.out.println(nodes);
            // 取出权值最小的两个二叉树
            Node left = nodes.get(0);
            Node right = nodes.get(1);
            // 得到新的二叉树
            int max = left.getValue() + right.getValue();
            Node maxNode = new Node(max);
            maxNode.setLeft(left);
            maxNode.setRight(right);
            // 擦除原来的两个二叉树
            nodes.remove(left);
            nodes.remove(right);
            // 新的二叉树放回集合
            nodes.add(maxNode);
        }
        return nodes.get(0);
    }
}
